Securing communication in distributed networks like the internet or mobile communication networks, e.g. 3G or LTE is a building block for a large number of applications. Conventional methods for securing communication are based for example on the SSL, IPSEC or SSH protocol. These protocols have been developed or designed decades ago when the underlying network topology was end-to-end oriented, meaning a client-to-server communication. A key requirement was to assess the confidentiality of the message and the message integrity. Any modification of messages was regarded as security breach.
One of the problems of using such protocols is, that they limit the flexibility of applications. Communication today is coupled more loosely. For example, in cloud-computing multiple parties interact with different services which are again distributed on different physical machines. For instance, the cloud provider contracts some web accelerator to embed a message template on the behalf of the cloud into the communication between a mobile device and the cloud provider. Usage of conventional security protocols does not allow the web accelerator to engage in the corresponding communication. To overcome this problem, service providers disseminate their secret key material, for example in form of long term keys, to intermediates.
However, this raises great security problems: Intermediates may easily impersonate the service provider and cause damage, for example by exploiting information of users of the service provider or the like. Since conventional secure protocols are designed in such a way that minor modifications to a message yield to a message rejection, even minor changes are delicate and require much care.
In the non-patent literature of Agrawal and Boneh, Homomorphic MACS: MAC-Based Integrity for Network Coding, in: ACNS 2009, LNCS 5536, pp. 292-305 a homomorphic message authentication code for network coding is described. Intermediate nodes in the underlying network may combine authenticated messages while preserving authenticity. In the non-patent literature of Boneh and Freeman, in: PKC'11 linearly homomorphic signatures for small fields are described. Even further a generized method for obtaining homomorphic signatures from previous signature schemes are described. Even further the homomorphism was extended to polynomial function as described in Boneh and Freeman, Homomorphic Signatures for Polynomial Functions, in: EUROCRYPT'12. One of the drawbacks of the above mentioned methods is that these methods are only useful for asymmetric settings due to the use of digital signatures where a signer and a verifier have different key material. However, digital signatures are useless when modifying encrypted messages.
In the non-patent literature of Ahn, Boneh, Camenisch, Hohenberger, Shealt, Waters: Computing on Authenticated Data, in: TCC 2012:1-20 an orthogonal method for computing on encrypted data is described. Message tags are derived for a message being valid relative to a predicate over a previous set of messages. In the non-patent literature of Rosario Gennaro, Daniel Wichs: Fully Homomorphic Message Authenticators, IACR Cryptology ePrint Archive 2012: 290 (2012) fully homomorphic message authenticators are defined using an underlying primitive fully-homomorphic encryption mechanism. However, one of the drawbacks is, that one is limited to compute a polynomial function over the messages while preserving the validity of accumulated message tags.